package pri.zjy.linkedList;

import java.util.HashMap;
import java.util.Map;

/**
 * @author zhangjy
 * @description 请你设计并实现一个满足  LRU (最近最少使用) 缓存 约束的数据结构。
 * @date 2025/2/20 10:07
 */
public class LRUCache_146 {

    public static void main(String[] args) {

        LRUCache_146 lruCache = new LRUCache_146(2);
        lruCache.put(1, 1);
        lruCache.put(2, 2);
        System.out.println(lruCache.get(1));
        lruCache.put(3, 3);
        System.out.println(lruCache.get(2));
        lruCache.put(4, 4);
        System.out.println(lruCache.get(1));
        System.out.println(lruCache.get(3));
        System.out.println(lruCache.get(4));
    }

    /**
     * 官解：map+双链表
     * <p>
     * 分析：
     * LRU，即最近最少使用；put、get要求为O(1)；
     * 1.首先，要体现最近使用，可以按顺序体现时间轴；
     * 2.其次，还还要体现最少使用，就需要移动，若已存在的数据再次put，需要放到最前面；
     * 3.put：先判断新元素是否存在，若存在，则更新key对应的value，再把其放到最前面（即最近使用）；反之，根据容量是否已满来决定插入新节点node的逻辑（若容量已满，则插入node后，还要删除尾部节点；反之，直接插入node即可）。
     * 3.1.查找——>放入；
     * 3.2.查找：不管数组、链表，都是O(n)
     * 3.3.放入，会涉及移动，从而体现时间轴；若数组，O(n)；若单链表，O(1)。
     * 4.get：直接获取元素，O(1)，且get的元素会放到时间轴最前面
     * 4.1.get涉及移动，体现时间轴；
     * 4.2.数组，O(n)；
     * 5.数据结构？
     * 5.1.通常使用栈实现，而栈底层又是用数组或链表实现；
     * 5.2.方法get，查找：数组O(n)、链表O(n)；放入：数组0(1)，单链表O(n)；
     * 5.3.方法put，数组O(n)，链表O(1);
     * 5.4.不管数组，还是链表，都无法满足O(1)，那么到底什么数据结构，在查找、新增时能够实现O(1)？
     * ——没有单一数据结构可以实现，考虑多种数据结构实现；
     * （1）HashMap，查找和增删都是O(1)，但是key无序，无法体现时间轴；
     * （2）数组、链表都可以体现时间轴，但是若数组，增删O(n)；而链表增删是O(1)，所以考虑链表，另外增删时为避免遍历链表，还得是双向链表
     */

    // 双向链表
    class DoubleLinkedListNode {

        private Integer key;

        private Integer value;

        DoubleLinkedListNode prev;

        DoubleLinkedListNode next;

        public DoubleLinkedListNode() {

        }

        public DoubleLinkedListNode(Integer key, Integer value, DoubleLinkedListNode prev, DoubleLinkedListNode next) {
            this.key = key;
            this.value = value;
            this.prev = prev;
            this.next = next;
        }

    }

    private Map<Integer, DoubleLinkedListNode> cacheMap;

    private DoubleLinkedListNode head;

    private DoubleLinkedListNode tail;

    private int capacity;

    private int size;

    public LRUCache_146(int capacity) {
        cacheMap = new HashMap<>(capacity);
        // 虚拟头、尾节点
        head = new DoubleLinkedListNode();
        tail = new DoubleLinkedListNode();
        head.next = tail;
        tail.prev = head;
        this.capacity = capacity;
        this.size = 0;
    }

    public int get(int key) {
        // 查找——>若有，则将对应key移动到最前面；若无，返回-1
        DoubleLinkedListNode node = cacheMap.get(key);
        if (node == null) {
            return -1;
        }
        // 移动key对应节点到头部
        // 1.移走node
        removeNode(node);
        // 2.head后插入node
        addNodeToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        // 先查找，再移动：若找到，则将对应key移动到最前面；反之，直接插入到最前面
        DoubleLinkedListNode node = cacheMap.get(key);

        // 1.找不到，则头部插入新节点
        if (node == null) {
            DoubleLinkedListNode newNode = new DoubleLinkedListNode(key, value, head, head.next);
            // 把newNode插入到头部
            addNodeToHead(newNode);

            // 若缓存已有数量 == 容量，则应删除最近最少使用的数据，即尾部节点
            if (size == capacity) {
                // 移除尾部节点temp
                DoubleLinkedListNode temp = tail.prev;
//                temp.prev.next = tail;
//                tail.prev = temp.prev;
                removeNode(tail.prev);
                // 从缓存中移除
                cacheMap.remove(temp.key);
                size--;
            }
            // newNode存入缓存
            cacheMap.put(key, newNode);
            size++;
            return;
        }

        // 2.找到，则移动node到头部
        // 2.1.更新缓存
        node.value = value;
        // 若已经在头部，则不移动
        if (node.prev == head) {
            return;
        }
        // 2.2.移动node到头部
        // 移走node
        removeNode(node);
        // head后插入node
        addNodeToHead(node);
    }

    /**
     * head->node——>head的原next：head的原next的前驱指向node，原next的新prev指向node；head的新next指向node，node的新prev指向head
     */
    private void addNodeToHead(DoubleLinkedListNode node) {
        // 1.旧next和新node指向彼此
        head.next.prev = node;
        node.next = head.next;
        // 2.head和新node指向彼此
        head.next = node;
        node.prev = head;
    }

    /**
     * 待移动节点node的原prev和原next指向彼此
     */
    private void removeNode(DoubleLinkedListNode node) {
        // node的前驱节点和后继节点指向批次，从而移除node
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

}
